Majority element II

Time: O(N); Space: O(1); medium

Given an integer array of size N, find all elements that appear more than [N/3] times.

Note:

• The algorithm should run in linear time and in O(1) space.

Example 1:

Input: nums = [3,2,3]

Output: [3]

Example 2:

Input: nums = [1,1,1,3,3,2,2,2]

Output: [1,2]

import collections

class Solution1(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        k, n, cnts = 3, len(nums), collections.defaultdict(int)

        for i in nums:
            cnts[i] += 1
            # Detecting k items in cnts, at least one of them must have exactly one in it.
            # We will discard those k items by one for each.
            # This action keeps the same mojority numbers in the remaining numbers.
            # Because if x / n  > 1 / k is true, then (x - 1) / (n - k) > 1 / k is also true.
            if len(cnts) == k:
                # for j in cnts.keys():
                # as python3 makes the keys() method an iterator, and also disallows deleting dict items during iteration.
                # By adding a list() call you turn the keys() iterator into a list.
                # So when you are in the body of the for loop you are no longer iterating over the dictionary itself.
                for j in list(cnts.keys()):
                    cnts[j] -= 1
                    if cnts[j] == 0:
                        del cnts[j]

        # Resets cnts for the following counting.
        for i in cnts.keys():
            cnts[i] = 0

        # Counts the occurrence of each candidate integer.
        for i in nums:
            if i in cnts:
                cnts[i] += 1

        # Selects the integer which occurs > [n / k] times.
        result = []
        for i in cnts.keys():
            if cnts[i] > n // k:
                result.append(i)

        return result

s = Solution1()
nums = [3,2,3]
assert s.majorityElement(nums) == [3]
nums = [1,1,1,3,3,2,2,2]
assert s.majorityElement(nums) == [1,2]

import collections

class Solution2(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return [i[0] for i in collections.Counter(nums).items() if i[1] > len(nums) // 3]

s = Solution2()
nums = [3,2,3]
assert s.majorityElement(nums) == [3]
nums = [1,1,1,3,3,2,2,2]
assert s.majorityElement(nums) == [1,2]

See also:

https://leetcode.com/problems/majority-element-ii

https://www.lintcode.com/problem/majority-element-ii